package com.nl.trees;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
public class BTree<T> {

	public BTree() {
	}
	
	public  static class Node<T> {
		Node<T> left;
		Node<T> right;
		T value;
	}
	
	Node<T> root;

	void build(T[]preOrder,T[]inorder){
		if(preOrder==null || inorder==null || preOrder.length!=inorder.length){
			throw new RuntimeException("invalid input");
		}
		this.root = buildRecursively(preOrder,0,preOrder.length-1,inorder,0,inorder.length-1);
	}

	
	/**
	 * 层次便利
	 */
	public void levelTranverse(){
		if(root!=null){
			Queue<Node<T>> queue = new ArrayBlockingQueue<BTree.Node<T>>(20);
			queue.offer(root);
			while(!queue.isEmpty()){
				Node<T> node = queue.poll();
				System.out.println(node.value+"\t");
				if(node.left!=null){
					queue.offer(node.left);
				}
				if(node.right!=null){
					queue.offer(node.right);
				}
			}
		}
	}
	/**
	 * 先序中序构造二叉树
	 * @param preOrder
	 * @param preStart
	 * @param preEnd
	 * @param inorder
	 * @param inStart
	 * @param inEnd
	 * @return
	 */
	private Node<T> buildRecursively(T[] preOrder, int preStart, int preEnd, T[] inorder,
			int inStart, int inEnd) {
		Node<T> root = new Node<T>();
		root.value = preOrder[preStart];
		if(preStart==preEnd){
			if(inStart==inEnd && preOrder[preStart]==inorder[inStart]){
				return root;
			}else{
				throw new RuntimeException("invalid input");
			}
		}

		int rootInorder = -1;
		for(int i=inStart;i<=inEnd;i++){
			if(inorder[i]==root.value){
				rootInorder =i;
				break;
			}
		}

		if(rootInorder == -1){
			throw new RuntimeException("invalid input");
		}

		int leftTreeLen=rootInorder-inStart;
		
		if(leftTreeLen>0){
			root.left = buildRecursively(preOrder, preStart+1,preStart+leftTreeLen, inorder, inStart, rootInorder-1);
		}

		if(preEnd-preStart>leftTreeLen){
			root.right = buildRecursively(preOrder, preStart+1+leftTreeLen, preEnd, inorder, rootInorder+1, inEnd);
		}

		return root;
	}
	
	public static void main(String[] args) {

		BTree<Integer> tree =new BTree<Integer>();
		tree.build(new Integer[]{1,2,4,3,5}, new Integer[]{4,2,1,3,5});

		tree.levelTranverse();

	}
}
